import codeJamUtils

def _compute_scores(case):
    return (_compute_optimal_deceitful_war_score(case), _compute_optimal_war_score(case))

def _compute_optimal_war_score(case):
    # in war, p1 has no information about the weights of p2's blocks. p1 can assume
    # that p2 will use a greedy algorithm; for each block B with weight W_b that she 
    # chooses, he will choose the block B' in his collection with weight W_b' > W_b
    # such that W_b' - W_b is minimized. If no such block exists, he will choose the
    # block in his collection with the smallest weight
    # The outcome in this case is fixed based on the initial weights of the blocks 
    # allocated to the two players. There is no way for p1 to cause p2 to unnecessarily
    # use a larger-weight block. Therefore to determine the optimal score for p1, we
    # simply simulate the game in any order of play.

    # these are assumed to be sorted
    p1BlockWeights, p2BlockWeights = case[0][:], case[1][:]
    p1Points = 0

    for p1Block in p1BlockWeights:
        p2Choice = None
        for p2Block in p2BlockWeights:
            if p2Block > p1Block:
                # win for p2
                p2Choice = p2Block
                break

        if p2Choice is None:
            # no winning block for p2 was found. point for p1
            p1Points += 1
            p2Choice = p2BlockWeights[0]

        p2BlockWeights.remove(p2Choice)
    
    return p1Points

def _compute_optimal_deceitful_war_score(case):
    return len(case[0]) - _compute_optimal_war_score((case[1], case[0]))
    
def _parse_input(lines):
    numCases = int(lines[0])
    cases = []

    for i in range(1, len(lines), 3):
        p1BlockWeights = sorted(map(lambda weightStr: float(weightStr), list(str.split(lines[i+1]))))
        p2BlockWeights = sorted(map(lambda weightStr: float(weightStr), list(str.split(lines[i+2]))))
        cases.append((p1BlockWeights, p2BlockWeights))

    return cases


if __name__ == "__main__":
    testCases = _parse_input(codeJamUtils.get_input_lines("deceitfulWar.txt"))
    for i, case in enumerate(testCases):
        scores = _compute_scores(case)
        codeJamUtils.write_output("deceitfulWar.txt", i + 1, str.format("{0} {1}", scores[0], scores[1]))

